package 算法.动态规划;

/**
 * @author Zhu
 * @Description
 * @create 2023-03-13
 */
public class JZ69跳台阶 {
    //递归 O(n2) O(1)
    public int jumpFloor(int target) {
        if(target<=1)
            return 1;
        return jumpFloor(target-1) + jumpFloor(target-2);
    }

    //记忆化搜索 O(n) O(n)
    int[] f = new int[50];
    public int jumpFloor2(int target) {
        if(target<=1)
            return 1;
        if (f[target] > 0) return f[target];
        return f[target] = (jumpFloor(target-1)+jumpFloor(target-2));
    }

    //动态规划 O(n) O(n)
    public int jumpFloor3(int target) {
        int[] dp = new int[50];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2;i<=target;i++)
            dp[i] = dp[i-1] + dp[i-2];
        return dp[target];
    }
    public int jumpFloor4(int target) {
        int a = 1 , b = 1 , c = 1;
        for (int i = 2 ; i <= target ; i ++) {
            c= a + b;
            a = b;
            b = c;
        }
        return  c;
    }
}
